Для настольной
игры используются карточки с номерами от 1 до n (натуральное число n не
превышает 106). Одна карточка потерялась. Найдите ее.
Вход. Первым задано число n. Далее следуют n – 1
номер оставшихся карточек.
Выход. Выведите номер потерянной карточки.
|
Пример
входа |
Пример
выхода |
|
5 1 2 3 4 |
5 |
РЕШЕНИЕ
математика – XOR
Анализ алгоритма
Решим задачу без использования массивов. Вычислим xor
операцию над всеми числами от 1 до n,
получив некоторый результат res.
Далее произведем операцию xor числа res
со всеми номерами оставшихся карточек. В результате получится номер потерянной
карточки.
Второе решение. Вычислим
сумму всех чисел от 1 до n. По
формуле арифметической прогрессии она равна res = (1 + n) * n / 2. Вычтем из res номера
всех карточек, имеющихся в наличии. После выполнения всех вычитаний res будет содержать номер потерянной
карточки.
Пример
Для заданного примера n
= 5. Сумма всех натуральных чисел от 1 до 5 равна
res = (1 + 5) * 5 / 2 = 15
Вычтем из res
номера оставшихся 4 карточек: 15 – 1 – 2 – 3 – 4 = 5. Получили 5 – номер потерянной
карточки.
Реализация алгоритма
Читаем входные данные. В переменной res вычислим xor операцию над всеми числами от 1 до n.
scanf("%d",&n);
res = 0;
for(i = 1; i <= n; i++) res ^= i;
Читаем номера оставшихся карточек
и совершаем операцию xor их со значением res.
for(i = 1; i < n; i++)
{
scanf("%d",&val);
res ^= val;
}
Выводим ответ.
printf("%d\n",res);
Реализация алгоритма – объединение циклов
#include <stdio.h>
int i, n, val, res;
int main(void)
{
scanf("%d",&n); res = n;
for(i = 1; i < n; i++)
{
scanf("%d",&val);
res ^= val ^ i;
}
printf("%d\n",res);
}
Java реализация Scanner, TLE 1.4 sec
import
java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int i, n = con.nextInt(), res = 0;
for(i = 1; i <= n; i++)
res ^= i;
for(i = 1; i < n; i++)
{
int val = con.nextInt();
res ^= val;
}
System.out.println(res);
con.close();
}
}
Java реализация FastScanner, 0.4 sec
import
java.util.*;
import
java.io.*;
class FastScanner
{
private BufferedReader br;
private StringTokenizer st;
public FastScanner(InputStreamReader reader)
{
br = new BufferedReader(reader);
}
public String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
} catch (Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
public void close() throws Exception
{
br.close();
}
}
public class Main
{
public static void main(String[] args)
{
FastScanner con =
new FastScanner(new
InputStreamReader(System.in));
int i, n = con.nextInt(), res = 0;
for(i = 1; i <= n; i++)
res ^= i;
for(i = 1; i < n; i++)
{
int val = con.nextInt();
res ^= val;
}
System.out.println(res);
}
}